package tree;

import org.junit.Test;

/**
 * @author DuJiabao
 * @create 2021-01-03 22:31
 */
public class ArrayTree<T> {
    private T[] tree; //从1开始存储
    private int count = 0;

    public ArrayTree() {
        tree = (T[]) new Object[2]; // 第一个位置不存储东西
    }

    ArrayTree(int size) {
        tree = (T[]) new Object[size];
    }

    public void addLeafNode(T value) {
        if (count + 1 >= tree.length) {
            resize(tree.length + (int) Math.pow(2, Math.floor(Math.log(tree.length - 1) / Math.log(2) + 1))); // 增加2的倍数个
        }
        tree[++count] = value;  //从1开始存储
    }

    private void resize(int size) {
        T[] temp = (T[]) new Object[size];
        for (int i = 0; i < tree.length; i++) {
            temp[i] = tree[i];
        }
        tree = temp;
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        preOrderRecursion(1);
        System.out.println();
    }

    private void preOrderRecursion(int point) {
        if (point > count) { // 1开始存储，因此count指向的，就是tree最后一个位置，当point大于count的时候，表示溢出了！
            return;
        }
        System.out.print(tree[point] + " ");
        preOrderRecursion(point * 2);
        preOrderRecursion(point * 2 + 1);
    }

    /**
     * 中序遍历
     */
    public void inOrder() {
        inOrderRecursion(1);
        System.out.println();
    }

    private void inOrderRecursion(int point) {
        if (point > count) { // 1开始存储，因此count指向的，就是tree最后一个位置，当point大于count的时候，表示溢出了！
            return;
        }
        inOrderRecursion(point * 2);
        System.out.print(tree[point] + " ");
        inOrderRecursion(point * 2 + 1);
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        postOrderRecursion(1);
        System.out.println();
    }

    private void postOrderRecursion(int point) {
        if (point > count) { // 1开始存储，因此count指向的，就是tree最后一个位置，当point大于count的时候，表示溢出了！
            return;
        }
        postOrderRecursion(point * 2);
        postOrderRecursion(point * 2 + 1);
        System.out.print(tree[point] + " ");
    }


    @Test
    public void test() {
        ArrayTree<Character> tree = new ArrayTree<Character>();
        tree.addLeafNode('A');
        tree.addLeafNode('B');
        tree.addLeafNode('C');
        tree.addLeafNode('D');
        tree.addLeafNode('E');
        tree.addLeafNode('F');
        tree.addLeafNode('G');
        tree.preOrder();
        tree.inOrder();
        tree.postOrder();
    }

}
